This invention relates generally to content-addressable memory (CAM), and in particular to CAM implementations on programmable logic devices.
Programmable logic devices (PLDs) are a well-known type of digital integrated circuit that may be programmed by a user (e.g., a logic designer) to perform specified logic functions. PLDs are becoming ever more popular, largely because they require less time to implement than semi-custom and custom integrated circuits.
FIG. 1 is a block diagram of one type of PLD, a field-programmable gate array (FPGA) 100. FPGA 100 includes an array of configurable logic blocks (CLBs) 105 that are programmably interconnected to each other and to programmable input/output blocks (IOBs) 110. The interconnections are provided by configurable horizontal and vertical interconnect lines 115 and 120, which may be connected to one another using programmable interconnect points (PIPs) 125. This collection of configurable elements may be customized by loading configuration data into internal configuration memory cells (not shown) that define how the CLBS, PIPS, and IOBs are configured. The configuration data may be read from memory (e.g., an external PROM) or written into FPGA 100 from an external device. The collective states of the individual memory cells then determine the function of FPGA 100. Some FPGAs also include block RAMS 130 that may be connected to other resources using interconnect lines.
FIG. 2 is a schematic diagram of a xe2x80x9cslicexe2x80x9d 200, one of two identical slices that make up an exemplary CLB in the Virtex(trademark) family of devices available from Xilinx, Inc. All of the terminals to and from slice 200 are connected to horizontal or vertical interconnect lines (see FIG. 1) through which they can be programmably connected to various other components within the FPGA.
Slice 200 includes two 4-input look-up tables (LUTS) 205A and 205B. LUTs 205A and 205B are each capable of implementing any arbitrarily defined Boolean function of up to four inputs. In addition, each of LUTs 205A and 205B can provide a 16xc3x971-bit synchronous RAM. Furthermore, the two LUTs can be combined to create a 16xc3x972-bit or 32xc3x971-bit synchronous RAM, or a 16xc3x971-bit dual-port synchronous RAM.
Slice 200 also includes a pair of sequential storage elements 210A and 210B that can be configured either as edge-triggered D-type flip-flops or as level-sensitive latches. The D inputs can be driven either by LUTs 205A and 205B or directly from input terminals, bypassing LUTs 205A and 205B. Each storage element includes an initialization terminal INIT, a reverse-initialization terminal R, an enable-clock terminal EC, and a clock terminal conventionally designated using the symbol xe2x80x9c greater than xe2x80x9d. The INIT terminal forces the associated storage element into an initialization state specified during configuration; the reverse-initialization terminal R forces the storage element in the opposite state as the INIT terminal. Terminals INIT and R can be configured to be synchronous or asynchronous, and the sense of each control input can be independently inverted.
As discussed above in connection with FIG. 1, configuration memory cells define the functions of the various configurable elements of slice 200. An exemplary two-input multiplexer 225 includes a pair of MOS transistors having gate terminals controlled by inverting and non-inverting terminals of configuration memory cell 230. Other configuration memory cells used to define the functions of the remaining programmable elements of slice 200 are omitted for brevity. The use of configuration memory cells to define the function of programmable logic devices is well understood in the art.
A detailed discussion of slice 200 is not necessary for understanding the present invention, and is therefore omitted for brevity. For a more detailed treatment of the operation of many components within slice 200, see the following U.S. patents and applications:
Ser. No. 08/786,818 entitled xe2x80x9cConfigurable Logic Block with AND Gate for Efficient Multiplication in FPGAs,xe2x80x9d by Chapman et al.,
Ser. No. 08/754,421, now U.S. Pat. No. 5,889,413 entitled xe2x80x9cLookup Tables Which Double as Shift Registers,xe2x80x9d by Bauer; and
Ser. No. 08/806,997, now U.S. Pat. No. 5,914,616 entitled xe2x80x9cFPGA Repeatable Interconnect Structure with Hierarchical Interconnect Lines,xe2x80x9d by Young, et al.
Each of the foregoing documents is incorporated herein by reference.
Content Addressable Memories (CAMs) are a class of parallel matching circuits. CAMs are traditionally employed in cache controllers for central processing units (CPUs). More recently, CAMs have become popular for use in telecommunications and networking. For example, as data packets arrive into a network router, processing of these packets typically depends on the network destination address of the packet. Because of the large number of potential addresses, and increasing performance demands, CAMs are used to retrieve the destination addresses of packets to speed data access.
CAM circuits are similar in structure to traditional random-access memory (RAM) circuits. Like RAM, CAM may be used to store binary data. Unlike RAM, however, CAM provides a xe2x80x9cmatch modexe2x80x9d that permits all of the data in CAM to be searched in parallel. In the match mode, each memory location in the CAM is compared in parallel with some value; if the value is found in one of the memory locations, the CAM produces a xe2x80x9cmatchxe2x80x9d signal.
In some CAM implementations, it is desirable to know the address of the memory location in which data is found. Thus, rather than producing a simple match signal, some CAM implementations supply the address of the matching data. In a sense, this is functionally opposite to that of a typical RAM: that is, RAM supplies data in response to an address, whereas CAM supplies an address in response to data. FIGS. 3A and 3B respectively depict a RAM 300 and a CAM 310 to illustrate the relative functionality of RAM and CAM.
CAM is a type of digital circuit, and may therefore be implemented in a programmable logic device, such as FPGA 100 of FIG. 1. The general approach is to provide an array of registers for data storage. A collection of comparators then determines whether a given input sample matches data in the registers.
FIG. 4 depicts an illustrative CAM circuit 400 implemented on an FPGA. CAM circuit 400 includes N registers R(1) through R(N) connected to N respective comparators C(1) through C(N). Registers R(1)-R(N) are typically made up of flip-flops, and comparators C(1)-C(N) are typically combinatorial logic. The flip-flops and combinatorial logic are generally located within the CLBs of an FPGA. For those implementations that require an address in addition to match notification, a decoder 410 connected to each match line M(1)-M(N) decodes the match-line signals to produce a unique address for each match. For a more detailed discussion of CAM designs for use in programmable logic devices, see:
xe2x80x9cAn Overview of Multiple CAM Designs in Virtex Family Devices,xe2x80x9d by Jean-Louis Brelet, XAPP 201, Sep. 23, 1999 (Version 1.1);
xe2x80x9cContent Addressable Memory (CAM) in ATM Applications,xe2x80x9d by Marc Defossez, XAPP202, Sep. 23, 1999 (Version 1.1);
xe2x80x9cDesigning Flexible, Fast CAMs with Virtex Family FPGAs,xe2x80x9d by Jean-Louis Brelet and Bernie New, XAPP203, Sep. 23, 1999 (Version 1.1); and
xe2x80x9cUsing Block SelectRAM+ for High-Performance Read/Write CAMs,xe2x80x9d by Jean-Louis Brelet, XAPP204 (Version 1.1) Oct. 1, 1999.
The above documents are incorporated herein by reference.
Conventional FPGA CAM circuits are viable. However, implementing comparators using programmable logic produces circuits that are too large for some applications. Furthermore, FPGA CAMs that rely on flip-flops for data storage are restricted by the number of flip-flops in the FPGA. While this is adequate for small designs, larger CAMs quickly deplete the resources of even the largest FPGAs. There is therefore a need for a more space efficient means of implementing CAMs using programmable logic.
The present invention makes use of the run-time reconfigurability of modern programmable logic devices to efficiently implement a CAM circuit using programmable logic. Rather than using configurable logic to compare CAM entries stored in flip-flops, a CAM in accordance with the invention uses reconfigurable logic for both data storage and comparison. Consequently, the number of available data registers (e.g., flip-flops) does not limit CAM size.
Reducing or eliminating the need for data registers preserves registers for other tasks. Moreover, the comparison circuitry need not allocate input terminals to register outputs, and can therefore accept a greater number of data bits. Conventional CAM designs instantiated in programmable logic require that at least half of the compare-circuit input terminals connect to storage registers, leaving the remaining terminals for data input. In contrast, compare circuitry in CAM designs in accordance with the invention use more than half (and typically all) of their input terminals for data input. Compare circuits in accordance with the invention therefore pack more efficiently into programmable logic.
A CAM in accordance with one embodiment of the invention includes a number of programmable look-up tables on a programmable logic device collectively configured to produce a xe2x80x9cmatchxe2x80x9d signal in response to data provided on a series of data input terminals. Configuration data determines the particular pattern to which the CAM responds, so new CAM entries are introduced by configuring (or reconfiguring) one or more of the look-up tables. A processor connected to the PLD responds to new CAM entries by executing instructions that first translate the new CAM entries into configuration data and then employ the configuration data to reprogram the PLD.
Their reconfigurable nature allows CAM circuits in accordance with the invention to be dynamically sized, even at run-time (i.e., even when the CAM circuit is operational). Dynamic sizing opens the possibility of not only changing the contents of the reconfigurable CAM (RCAM) during operation, but also of changing the size and shape of the RCAM circuit itself. RCAM circuits are therefore analogous to dynamic memory allocation in RAM: it is possible to xe2x80x9callocatexe2x80x9d and xe2x80x9cfreexe2x80x9d CAM resources as needed by an application.
This summary does not limit the invention, which is instead defined by the appended claims.